/*
___A
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
const int maxN = 1e5*2 + 7;
int n, q;
int a[maxN];
int st[4 * maxN];
void build(int id, int l, int r) {
if (l == r) {
st[id] = a[l];
return;
}
int mid = l + r >> 1;
build(2 * id, l, mid);
build(2 * id + 1, mid + 1, r);
st[id] = min(st[2 * id], st[2 * id + 1]);
}
void update(int id, int l, int r, int i, int val) {
if (l > i || r < i) return;
if (l == r) {
st[id] = val;
return;
}
int mid = l + r >> 1;
update(2 * id, l, mid, i, val);
update(2 * id + 1, mid + 1, r, i, val);
st[id] = min(st[2 * id], st[2 * id + 1]);
}
int get(int id, int l, int r, int u, int v) {
if (l > v || r < u) return inf;
if (l >= u && r <= v) return st[id];
int mid = l + r >> 1; // (l + r) / 2
int get1 = get(2 * id, l, mid, u, v);
int get2 = get(2 * id + 1, mid + 1, r, u, v);
return min(get1, get2);
}
int main() {
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) update(1, 1, n, x, y);
else cout << get(1, 1, n, x, y) << '\n';
}
}
___B
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxN = 1e5*2 + 7;
ll n, q;
ll a[maxN];
ll st[4 * maxN];
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = a[l];
return;
}
ll mid = l + r >> 1;
build(2 * id, l, mid);
build(2 * id + 1, mid + 1, r);
st[id] =st[2 * id] + st[2 * id + 1];
}
void update(ll id, ll l, ll r, ll i, ll val) {
if (l > i || r < i) return;
if (l == r) {
st[id] = val;
return;
}
ll mid = l + r >> 1;
update(2 * id, l, mid, i, val);
update(2 * id + 1, mid + 1, r, i, val);
st[id] =st[2 * id] + st[2 * id + 1];
}
ll get(ll id, ll l, ll r, ll u, ll v) {
if (l > v || r < u) return 0;
if (l >= u && r <= v) return st[id];
ll mid = l + r >> 1;
ll get1 = get(2 * id, l, mid, u, v);
ll get2 = get(2 * id + 1, mid + 1, r, u, v);
return get1 + get2;
}
int main() {
cin >> n >> q;
for (ll i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
while (q--) {
ll type, x, y;
cin >> type >> x >> y;
if (type == 1) update(1, 1, n, x, y);
else cout << get(1, 1, n, x, y) << '\n';
}
}
___C
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxN = 1e5*2 + 7;
ll n, q;
ll a[maxN];
ll lazy[4 * maxN];
ll st[4 * maxN];
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = a[l];
return;
}
ll mid = l + r >> 1;
build(2 * id, l, mid);
build(2 * id + 1, mid + 1, r);
st[id] =max(st[2 * id], st[2 * id + 1]);
}
void fix(ll id, ll l, ll r){
if(lazy[id] == 0) return;
st[id] += lazy[id];
if(l != r){
lazy[2 * id + 1] += lazy[id];
lazy[2 * id] += lazy[id];
}
lazy[id] = 0;
}
void update(ll id, ll l, ll r, ll u, ll v, ll val){
fix(id,l,r);
if(l > v || r < u) return;
if(l >= u && r <= v){
lazy[id] += val;
fix(id,l,r);
return;
}
ll m = l + r >> 1;
update(2 * id, l, m, u, v, val);
update(2 * id + 1, m + 1, r, u, v, val);
st[id] = max(st[id * 2],st[id * 2 + 1]);
}
ll get(ll id, ll l, ll r, ll u, ll v){
fix(id,l,r);
if(l > v or r < u) return -1;
if(l >= u and r <= v) return st[id];
ll m = l + r >> 1;
ll get1 = get(2 * id, l, m, u, v);
ll get2 = get(2 * id + 1, m + 1, r, u, v);
return max(get1,get2);
}
int main() {
cin >> n >> q;
for (ll i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
while (q--) {
ll x;
cin >> x;
if(x == 1){
ll y, z, t;
cin >> y >> z >> t;
update(1, 1, n, y, z, t);
} else {
ll y;
cin >> y;
cout << get(1, 1, n, y, y) << endl;
}
}
}
__E shortcut
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxN = 1e5*2 + 7;
ll n, q;
ll a[maxN];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (ll i = 1; i <= n; ++i) cin >> a[i];
cin >> q;
while (q--) {
ll x, y, z;
cin >> x >> y >> z;
ll sum = 0;
if(x == 1){
for( ll i = y; i <= z; ++i ){
sum += a[i];
}
cout << sum << endl;
}
else{
ll r;
cin >> r;
for( ll i = y; i <= z; ++i ){
a[i] ^= r;
}
}
}
}
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int arr[N];
int gcd(int a,int b)
{
{int t;while(b){a=a%b;t=a;a=b;b=t;}return a;}
}
struct segment{
int _gcd;
int _count;
segment(){
_gcd=0;
_count=0;
}
segment(int val)
{
_gcd=val;
_count=1;
}
void mergee(segment left,segment right)
{
_count=0;
_gcd=gcd(left._gcd,right._gcd);
if(_gcd==left._gcd)
{
_count+=left._count;
}
if(_gcd==right._gcd)
{
_count+=right._count;
}
}
}seg[4*N];
void build(int low,int high,int node)
{
if(low>high)
return;
if(low == high)
{
seg[node]=segment(arr[low]);
return;
}
int mid=low+high>>1;
build(low,mid,2*node+1);
build(mid+1,high,2*node+2);
seg[node].mergee(seg[2*node+1],seg[2*node+2]);
}
segment query(int low,int high,int lq,int hq,int node)
{
if(low>high||low>hq||high<lq)
return segment();
if(lq<=low && high<=hq) { return seg[node]; } int mid=low+high>>1;
segment temp=segment();
temp.mergee(query(low,mid,lq,hq,2*node+1),query(mid+1,high,lq,hq,2*node+2));
return temp;
}
int main() {
int n;
scanf("%d",&n);
register int i;
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
build(0,n-1,0);
int t,l,r;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&l,&r);
printf("%d\n",(r-l+1)-query(0,n-1,l-1,r-1,0)._count);
}
return 0;
}
More_segtree
__A
#include <bits/stdc++.h>
using namespace std;
long long doot[500001][26]{0};
long long int deco(string str , int l , int r , int sqr)
{
long long int c[26]{0};
while(l%sqr!=0 && l<=r)
{
c[str[l]-97]++;
l++;
}
while(l+sqr<=r)
{
for(int j=0 ; j<26 ; j++)
c[j]+=doot[l/sqr][j] ;
l+=sqr;
}
while(l<=r)
{
c[str[l]-97]++;
l++;
}
long long int distinct = 0 ;
for(int j=0 ; j<26 ; j++)
{
if(c[j]>0)
distinct++;
}
return distinct ;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
long long int n , q , k ;
string str = "" ;
cin >> str >> q ;
n = str.length();
long long int sqr = (long long int )sqrt(n) ;
long long int c = 0 ;
long long int ole = 0 ;
long long int flag = 0 ;
for(int i=0 ; i<n ; i++)
{
ole++;
doot[flag][str[i]-97]++;
if(ole==sqr)
{
flag++;
ole = 0 ;
}
}
while(q--)
{
int type ;
cin >> type ;
if(type==2)
{
int l , r ;
cin >> l>> r ;
cout << deco( str , l-1 , r-1 , sqr)<< "\n";
}
else
{
int p ;
char val ;
cin >> p >> val ;
p--;
int first = p / sqr ;
doot[first][str[p]-97]--;
doot[first][val-97]++;
str[p] = val;
}
}
}
__B
#include "bits/stdc++.h"
using namespace std;
const int inf = 1e9 +7 ;
#define up(j, n) for(int j=0; j < (n); j++)
#define down(j, n) for(int j= n-1; j >= 0; j--)
const int maxN = 2e6 + 5;
#define int long long
int st[4 * maxN];
int lazy[4 * maxN];
int a[maxN + 5];
void push(int id, int l, int r){
if(!lazy[id])return;
st[id] += lazy[id];
if(l != r){
lazy[2 * id + 1] += lazy[id];
lazy[2 * id] += lazy[id];
}
lazy[id] = 0;
}
void build(int id, int l, int r){
if(l == r){
st[id] = a[l];
return;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 +1, mid + 1, r);
st[id] = min(st[id * 2], st[id * 2 + 1]);
}
void update(int id, int tl, int tr, int ql, int qr, int val){
push(id, tl, tr);
if(tl > qr || tr < ql){
return;
}
if(tl >= ql && tr <= qr){
lazy[id] += val;
push(id, tl, tr);
return;
}
int mid = (tl + tr) / 2;
update(id * 2 , tl, mid, ql, qr, val);
update(id * 2 + 1, mid + 1, tr, ql, qr, val);
st[id] = min( st[id * 2 ] , st[id * 2 + 1] );
}
int queryRange(int id, int tl, int tr, int ql, int qr){
push(id, tl, tr);
if (ql > tr || tl > qr){
return inf;
}
if (ql <= tl && tr <= qr){
return st[id];
}
int tm = (tl + tr) / 2;
return min(queryRange(id * 2, tl, tm, ql, qr) , queryRange(id * 2 + 1, tm + 1, tr, ql, qr)) ;
}
int n, q;
signed main(){
cin >> n;
for(int j=1; j <= n; j++){
cin >> a[j];
}
build(1, 1 , n);
cin >> q;
cin.ignore();
while(q--){
string c;
string x;
getline(cin, c);
int count=0;
int l, r, val;
for(int j=0; j< c.size();j++){
if(c[j] != ' '){
x += c[j];
}
else{
if(count == 0){
l = stoi(x);
}
if(count == 1){
r = stoi(x);
}
x="";
count++;
}
}
if(count == 1) r = stoi(x);
if(count == 2) {
val = stoi(x);
if(l > r){
update(1, 1, n, l+1, n, val);
update(1, 1, n, 1, r+1, val);
}
else update(1, 1, n, l+1, r+1, val);
}
else {
if(l > r){
cout << min(queryRange(1, 1, n, l+1, n), queryRange(1, 1, n, 1, r+1)) << endl;
}
else cout << queryRange(1, 1, n, l+1, r+1) << endl;
}
}
}
__D*/
// (^-^)
// / >
// / |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxN = 1e6 + 7;
ll n, q;
ll a[maxN], D[maxN];
ll st[4 * maxN], mx[4 * maxN];
void div()
{
memset(D, 0, sizeof(D));
for (int i = 1; i < maxN; i++)
{
for (int j = i; j < maxN; j += i)
D[j]++;
}
}
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = a[l];
mx[id] = a[l];
return;
}
ll mid = (l + r) / 2;
build(2 * id, l, mid);
build(2 * id + 1, mid + 1, r);
st[id] =st[2 * id] + st[2 * id + 1];
mx[id] = max(st[2 * id], st[2 * id + 1]);
}
void update(ll id, ll l, ll r, ll i, ll val) {
if (val < l || r < i) return;
if(mx[id] <= 2) return;
if (l == r) {
st[id] = mx[id] = D[mx[id]];
return;
}
ll mid = (l + r) / 2;
update(2 * id, l, mid, i, val);
update(2 * id + 1, mid + 1, r, i, val);
st[id] =st[2 * id] + st[2 * id + 1];
mx[id] = max(mx[2 * id], mx[2 * id + 1]);
}
ll get(ll id, ll l, ll r, ll u, ll v) {
if (l > v || r < u) return 0;
if (l >= u && r <= v) return st[id];
ll mid = (l + r) / 2;
ll get1 = get(2 * id, l, mid, u, v);
ll get2 = get(2 * id + 1, mid + 1, r, u, v);
return get1 + get2;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
div();
cin >> n >> q;
for (ll i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
while (q--) {
ll type, x, y;
cin >> type >> x >> y;
if (type == 1) update(1, 1, n, x, y);
else cout << get(1, 1, n, x, y) << '\n';
}
}
229. Majority Element II | 222. Count Complete Tree Nodes |
215. Kth Largest Element in an Array | 198. House Robber |
153. Find Minimum in Rotated Sorted Array | 150. Evaluate Reverse Polish Notation |
144. Binary Tree Preorder Traversal | 137. Single Number II |
130. Surrounded Regions | 129. Sum Root to Leaf Numbers |
120. Triangle | 102. Binary Tree Level Order Traversal |
96. Unique Binary Search Trees | 75. Sort Colors |
74. Search a 2D Matrix | 71. Simplify Path |
62. Unique Paths | 50. Pow(x, n) |
43. Multiply Strings | 34. Find First and Last Position of Element in Sorted Array |
33. Search in Rotated Sorted Array | 17. Letter Combinations of a Phone Number |
5. Longest Palindromic Substring | 3. Longest Substring Without Repeating Characters |
1312. Minimum Insertion Steps to Make a String Palindrome | 1092. Shortest Common Supersequence |
1044. Longest Duplicate Substring | 1032. Stream of Characters |
987. Vertical Order Traversal of a Binary Tree | 952. Largest Component Size by Common Factor |